class Solution2 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Stack<TreeNode> stackP = new Stack<>();
        Stack<TreeNode> stackQ = new Stack<>();
        getPath(root,p,stackP);
        getPath(root,q,stackQ);

        int size = stackP.size() - stackQ.size();
        if(size>0) {
            while(size>0) {
                stackP.pop();
                size--;
            }
        }else {
            while(size<0) {
                stackQ.pop();
                size++;
            }
        }

        while(!stackP.isEmpty()) {
            if(stackP.peek() == stackQ.peek()) {
                return stackP.peek();
            }
            stackP.pop();
            stackQ.pop();
        }
        return null;
    }

    boolean getPath(TreeNode root,TreeNode node,Stack<TreeNode> stack) {
        if(root == null) return false;
        stack.push(root);

        if(root == node) {
            return true;
        }
        if(root.left==null&&root.right==null) {
            stack.pop();
            return false;
        }

        boolean ret = getPath(root.left,node,stack);
        if(ret==true) {
            return true;
        }
        ret = getPath(root.right,node,stack);
        if(ret==true) {
            return true;
        }

        stack.pop();
        return false;
    }
}